<!doctype html>


<html>
<head>
  <link rel="shortcut icon" href="static/images/favicon.ico" type="image/x-icon">
  <title>avltree.js (Closure Library API Documentation - JavaScript)</title>
  <link rel="stylesheet" href="static/css/base.css">
  <link rel="stylesheet" href="static/css/doc.css">
  <link rel="stylesheet" href="static/css/sidetree.css">
  <link rel="stylesheet" href="static/css/prettify.css">

  <script>
     var _staticFilePath = "static/";
  </script>

  <script src="static/js/doc.js">
  </script>

  <meta charset="utf8">
</head>

<body onload="prettyPrint()">

<div id="header">
  <div class="g-section g-tpl-50-50 g-split">
    <div class="g-unit g-first">
      <a id="logo" href="index.html">Closure Library API Documentation</a>
    </div>

    <div class="g-unit">
      <div class="g-c">
        <strong>Go to class or file:</strong>
        <input type="text" id="ac">
      </div>
    </div>
  </div>
</div>





<div class="colmask rightmenu">
<div class="colleft">
    <div class="col1">
      <!-- Column 1 start -->

<div id="title">
       <span class="fn">avltree.js</span>
</div>

<div class="g-section g-tpl-75-25">
  <div class="g-unit g-first" id="description">
    Datastructure: AvlTree.


 This file provides the implementation of an AVL-Tree datastructure. The tree
 maintains a set of unique values in a sorted order. The values can be
 accessed efficiently in their sorted order since the tree enforces an O(logn)
 maximum height.

 The big-O notation for all operations are below:
 <pre class="lang-js">
 Method                 big-O
 ----------------------------------------------------------------------------
 - add                    O(logn)
 - remove                 O(logn)
 - clear                  O(1)
 - contains               O(logn)
 - getCount               O(1)
 - getMinimum             O(1), or O(logn) when optional root is specified
 - getMaximum             O(1), or O(logn) when optional root is specified
 - getHeight              O(1)
 - getValues              O(n)
 - inOrderTraverse        O(logn + k), where k is number of traversed nodes
 - reverseOrderTraverse   O(logn + k), where k is number of traversed nodes
 </pre>
  </div>
  

        <div class="g-unit" id="useful-links">
          <div class="title">Useful links</div>
          <ol>
            <li><a href="closure_goog_structs_avltree.js.source.html"><span class='source-code-link'>Source Code</span></a></li>
          </ol>
        </div>
</div>

<h2 class="g-first">File Location</h2>
  <div class="g-section g-tpl-20-80">
    <div class="g-unit g-first">
      <div class="g-c-cell code-label">structs/avltree.js</div>
    </div>
  </div>
<hr/>


  <h2>Classes</h2>
 <div class="fn-constructor">
        <a href="class_goog_structs_AvlTree.html">
          goog.structs.AvlTree</a><br/>
        <div class="class-details">Constructs an AVL-Tree, which uses the specified comparator to order its
values. The values can be accessed efficiently in their sorted order since
the tree enforces a O(logn) maximum height.</div>
 </div>
 <div class="fn-constructor">
        <a href="class_goog_structs_AvlTree_Node.html">
          goog.structs.AvlTree.Node</a><br/>
        <div class="class-details">Constructs an AVL-Tree node with the specified value. If no parent is
specified, the node&#39;s parent is assumed to be null. The node&#39;s height
defaults to 1 and its children default to null.</div>
 </div>
      
<br/>

  <div class="legend">
        <span class="key publickey"></span><span>Public</span>
        <span class="key protectedkey"></span><span>Protected</span>
        <span class="key privatekey"></span><span>Private</span>
  </div>


  <h2>Global Functions</h2>





<div class="section">
  <table class="horiz-rule">


     <tr class="even entry private">
       <td class="access"></td>






  <td>
    <a name="goog.structs.AvlTree.DEFAULT_COMPARATOR_"></a>


     <div class="arg">
       <img align="left" src="static/images/blank.gif">

        <span class="entryNamespace">goog.structs.AvlTree.</span><span class="entryName">DEFAULT_COMPARATOR_<span class="args">(<span class="arg">a</span>,&nbsp;<span class="arg">b</span>)</span>
        </span>
        &#8658; <div class="fullType"><span class="type"><a href="http://www.google.com/url?sa=D&q=https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Number">number</a></span></div>
      </div>


     <div class="entryOverview">
       String comparison function used to compare values in the tree. This function
is used by default if no comparator is specified in the tree&#39;s constructor.
     </div>


    <! -- Method details -->
    <div class="entryDetails">

      <div class="detailsSection">
        <b>Arguments: </b>






<table class="horiz-rule">
     
   <tr class="even">
     <td>
        <span class="entryName">a</span>
        : <div class="fullType"><span class="type"><a href="http://www.google.com/url?sa=D&q=https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/String">string</a></span></div>
        <div class="entryOverview">The first string.</div>
     </td>
   </tr>
     
   <tr class="odd">
     <td>
        <span class="entryName">b</span>
        : <div class="fullType"><span class="type"><a href="http://www.google.com/url?sa=D&q=https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/String">string</a></span></div>
        <div class="entryOverview">The second string.</div>
     </td>
   </tr>
  </table>
      </div>
   
      <div class="detailsSection">
        <b>Returns:</b>&nbsp;<div class="fullType"><span class="type"><a href="http://www.google.com/url?sa=D&q=https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Number">number</a></span></div>&nbsp;
            -1 if a &lt; b, 1 if a &gt; b, 0 if a = b.
      </div>
  
    </div>
   
  </td>


  <td class="view-code">
     <a href="closure_goog_structs_avltree.js.source.html#line73">code &raquo;</a>
  </td>
     </tr>


  </table>
</div>






      <!-- Column 1 end -->
    </div>

        <div class="col2">
          <!-- Column 2 start -->
          <div class="col2-c">
            <h2 id="ref-head">Directory structs</h2>
            <div id="localView"></div>
          </div>

          <div class="col2-c">
            <h2 id="ref-head">File Reference</h2>
            <div id="sideFileIndex" rootPath="closure/goog" current="structs/avltree.js"></div>
          </div>
          <!-- Column 2 end -->
        </div>
</div>
</div>

</body>
</html>
